package com.whosly.demo.benchmark.sortalgorithms.merge;

import com.whosly.demo.benchmark.sortalgorithms.ISortingAlgorithms;

import java.util.Arrays;

/**
 * 归并排序（Merge Sort）
 *
 * @author fengyang
 * @date 2023/6/13 上午10:43
 * @see <a href="fengyang@stoneatom.com">mailTo: fengyang@stoneatom.com</a>
 */
public class MergeSort implements ISortingAlgorithms
{
    @Override
    public int[] sorting(int[] arr)
    {
        int len = arr.length;
        // 说明只有一个元素，此时不需要进行交换
        if (len < 2) {
            return arr;
        }

        // 将数组分成两部分
        int mIdx = len / 2;

        // 将两个子数组进行归并
        return merge(
                // 利用递归，将一个数组分成两个子数组
                sorting(Arrays.copyOfRange(arr, 0, mIdx)),
                sorting(Arrays.copyOfRange(arr, mIdx, len))
        );
    }

    private int[] merge(int[] arrLeft, int[] arrRight) {
        int leftLen = arrLeft.length, rightLen = arrRight.length, leftIdx = 0, rightIdx = 0, idx = 0;

        int[] result = new int[leftLen + rightLen];

        while (leftIdx < leftLen && rightIdx < rightLen) {
            //当两个子数组都有元素的时候，则将两者的元素进行比较，谁小的谁先插入到新的数组中，从而实现升序排序
            if (arrLeft[leftIdx] < arrRight[rightIdx]) {
                result[idx++] = arrLeft[leftIdx++];
            } else {
                result[idx++] = arrRight[rightIdx++];
            }
        }

        //考虑子数组的长度不一样的情况
        //当左子数组没有遍历完的时候
        while (leftIdx < leftLen) {
            result[idx++] = arrLeft[leftIdx++];
        }

        //当右子数组没有遍历完的时候
        while (rightIdx < rightLen) {
            result[idx++] = arrRight[rightIdx++];
        }

        return result;
    }
}
